package com.cty._03_SolutionSeekingMindset._31_StackPushPopOrder;

import java.util.Stack;

/**
 * @Auther: cty
 * @Date: 2020/7/11 9:53
 * @Description: 面试题31：栈的压入、弹出序列
 * 题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是
 * 否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、
 * 5是某栈的压栈序列，序列4、5、3、2、1是该压栈序列对应的一个弹出序列，但
 * 4、3、5、1、2就不可能是该压栈序列的弹出序列。
 *
 * 研究两个动态变化的对象
 * @version: 1.0
 */
public class StackPushPopOrder {

    public static boolean isPopOrder(int[] pushArray, int[] popArray, int length){
        if(pushArray==null || popArray==null || length==0)
            return false;

        boolean isPopOrder = false;
        Stack<Integer> stack = new Stack<>();
        int pushPtr = 0;
        int popPtr = 0;

        while(popPtr < length){
            while(stack.isEmpty() || stack.peek()!=popArray[popPtr]){
                if(pushPtr == length)
                    break;
                stack.push(pushArray[pushPtr++]);
            }

            if(stack.peek()!=popArray[popPtr])
                break;

            stack.pop();
            popPtr++;
        }

        if(stack.isEmpty() && popPtr==length)
            return true;
        return isPopOrder;
    }  // end isPopOrder()

}  // end class
